package org.chnxi.datastructures.search;

import java.util.Arrays;

/**
 * 斐波那契
 */
public class FibonacciSearching {

    static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};

        System.out.println(fibonacciSearch(arr , 1));
        System.out.println(fibonacciSearch(arr , 1234));
        System.out.println(fibonacciSearch(arr , 89));
        System.out.println(fibonacciSearch(arr , 12345));
    }

    /**
     * mid=low+F(k-1)-1，需要使用到斐波那契数列，因此先获取一个斐波那契数列
     */
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i=2; i < maxSize; i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    /**
     * 使用斐波那契方法查找
     * @param arr 数组
     * @param val 待查找的数值
     * @return 返回对应的下标，如果没有返回-1
     */
    public static int fibonacciSearch(int[] arr, int val){
        int low = 0;
        int high = arr.length-1;
        int k = 0; //表示斐波那契分割数值对应的下标
        int mid = 0;//存放mid值

        int[] f = fib(); //获取斐波那契数列

        //获取到斐波那契分割值的下标
        while(high > f[k] -1){
            k++;
        }

        //因为f[k]可能大于数组arr的长度，因此我们需要使用Arrays类构造一个新的数组，并指向arr
        //不足的部分，会使用0填充
        int[] tmp = Arrays.copyOf(arr , f[k]);
        //实际上需要使用arr数组最后的数填充tmp
        //举例：tmp={1,8,10,89,1000,1234,0,0} => {1,8,10,89,1000,1234,1234,1234}
        for (int i=high+1; i < tmp.length; i++){
            tmp[i] = arr[high];
        }

        //使用while循环处理，找到我们的key
        while (low <= high){
            mid = low + f[k-1]-1;
            if(val < tmp[mid]){ //我们应该向数组的左边查找
                high = mid - 1;
                //说明：
                // 1. 全部元素 = 前面的元素 + 后面的元素
                // 2. f[k] = f[k-1] + f[k-2]
                // 3. 因为前面有f[k-1]个元素，所以可以继续拆分f[k-1]=f[k-2]+f[k-3]
                // 4. 即在f[k-1]的前面继续查找，k--
                // 5. 即下次循环mid = f[k-1-1]-1
                k--;
            }else if(val > tmp[mid]){
                low = mid + 1;
                //说明：
                // 1. 全部元素 = 前面的元素 + 后面的元素
                // 2. f[k] = f[k-1] + f[k-2]
                // 3. 因为后面我们有f[k-2]个元素，所以可以继续拆分f[k-1] = f[k-3] + f[k-4]
                // 4. 即在f[k-2]的前面进行查找，f-=2
                // 5. 即下次循环mid = f[k-1-2]-1
                k -=2;
            }else{
                if(mid <= high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }

}
